package leetcode;
/**
 * 32.最长有效括号
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 * 输入：s = ""
 * 输出：0
 */
public class Num_32 {
    //动态规划
    public int longestValidParentheses(String s) {
        //一定不符合条件的情况
        if(s.length() < 2){
            return 0;
        }
        /**
         * 我们用 dp[i] 表示以 i 结尾的最长有效括号；
         *当 s[i] 为 '(' 时,dp[i] 必然等于 0，因为不可能组成有效的括号；
         * 那么 s[i] 为 ')'时，
         *    当 s[i-1] 为 '('时，那么 dp[i] = dp[i-2] + 2；
         *    当 s[i-1] 为 ')' 并且 s[i-dp[i-1] - 1]为 '('时，那么 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]；
         */
        //dp[i]表示以i结尾的有效括号的长度
        int[] dp = new int[s.length()];
        //初始化
        dp[0] = 0;
        int maxL = 0;
        for(int i = 1; i < s.length(); i++){
            if(s.charAt(i) == '('){
                dp[i] = 0;
            }else{
                //s.charAt(i) == ')'
                if(s.charAt(i - 1) == '('){
                    // "...()"
                    dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;
                }else{
                    //".....))"
                    if(i-dp[i-1]-1 >= 0 && s.charAt(i-dp[i-1] - 1) == '('){
                        dp[i] = i-dp[i-1]-2 >= 0 ? dp[i-1] + 2 + dp[i-dp[i-1]-2] : dp[i-1] + 2;
                    }
                }
            }
            maxL = Math.max(maxL, dp[i]);
        }
        return maxL;
    }
}
